package com.kk.datastructure.tree.availabletree.huffman;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * title: 赫夫曼编码(字符串数据压缩与解压)
 * @author 阿K
 * 2021年1月10日 下午9:49:33 
 */
public class HuffmanCode {

	public static void main(String[] args) {

		/* 第一大步骤测试 ：步骤一 至三，主要实现 通过字符串的字节数组构建赫夫曼数*/
		String content = "i like like like java do you like a java";
		byte[] contentBytes = content.getBytes();
		List<Node> nodes = getNodes(contentBytes);
	//	System.out.println("有效节点个数为：" + nodes.size());// 12 个有效节点
		Node root = createHuffmanTree(nodes);
//		System.out.println("前序遍历当前赫夫曼树：");
		perOrder(root);
		
		/* 第二大步测试 ：步骤四 ，主要实现 通过赫夫曼树生成对应的赫夫曼编码表 */
		Map<Byte,String> codes = getCodes(root);
		System.out.println(codes);
		
		/* 第三大步测试 ：步骤五 主要实现，压缩字符串，生成赫夫曼规则的字节数组 */
//		System.out.println(Arrays.toString(zip(contentBytes, huffmanCodes)));;
		byte[] huffmanBytes = huffmanZip(contentBytes);
		System.out.println(Arrays.toString(huffmanBytes));
		
		/* 第四大步测试 ：步骤六至 七 ，主要实现，解压缩字符串，逆向操作 */
		byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
		System.out.println(new String(sourceStr));
	}
	
	
	// 步骤七内容-----------------------------------------------------
	// 字符串解压思路：
	// 1.将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
	//先转成赫夫曼编码对应的二进制的字符串 "1010100010111..."
	// 2.再将 此二进制字符串  对照赫夫曼编码表(反向) 转成 最初字符串的二进制字节数组
	public static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes) {
		//1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
		StringBuilder stringBuilder = new StringBuilder();
		// 将 byte 数组转成 二进制字符串
		for (int i = 0; i < huffmanBytes.length; i++) {
			byte b = huffmanBytes[i];
			// 判断是否为最后一个字节
			boolean flag = ( i == huffmanBytes.length-1);
			stringBuilder.append(byteToBitString(!flag, b));
		}
		
		// 2.把字符串按照指定的赫夫曼编码进行解码
		// 把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
		Map<String,Byte> map = new HashMap<>();
		for(Map.Entry<Byte, String> entry:huffmanCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		
		// 3.创建用于存放 byte的集合
		List<Byte> list = new ArrayList<>();
		// 其中 i 在这里充当索引，用于扫描 stringBuilder
		for (int i = 0; i < stringBuilder.length();) {
			int count = 1;// 微型计算器，用于记录内部的 while循环,与 i相辅相成
			boolean flag = true;// 用于控制 while
			Byte b = null;// 记录要存放的字节
			
			while(flag) {
				// 1010100010111...
				// 递增的取出 key 1 ,没有再移动 10  ，101 以此类推
				String key = stringBuilder.substring(i,i+count);// i不动，count移动，指定匹配到一个字符(0或1)
				b = map.get(key);				
				if(b == null) {
					// 说明没有匹配到
					count++;
				}else {
					// 匹配到
					flag = false;
				}
			}
			list.add(b);
			i += count; // i 直接移动到 count(若 while 中 符合条件的次数 count 达到则 退出，次数 i也没必要移动，此处 i才是辅助)
		}
		
		// 4.以上循环结束后，说明已经解码结束
		byte[] bytes = new byte[list.size()];
		for (int i = 0; i < list.size(); i++) {
			bytes[i] = list.get(i);
		}
		return bytes;
	}
	
	// 步骤六内容-----------------------------------------------------
	public static String byteToBitString(boolean flag,byte b) {
		// 将 b 转成 int
		int temp = b;
		// 若是正数，则需要补高位,转换需要 int 类型
		if(flag) {
			// 按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
			temp |=256;
		}
		// 返回的是 temp 对应的二进制补码
		String str = Integer.toBinaryString(temp);
		if(flag) {
			return str.substring(str.length()-8);
		}
		// 若不是正数直接返回
		return str;
	}
	
	
	
	// 封装以下步骤(1-5)所有关于压缩字符串的代码
	public static byte[] huffmanZip(byte[] bytes) {
		List<Node> nodes = getNodes(bytes);
		// 根据 nodes 创建的赫夫曼树
		Node huffmanTreeRoot = createHuffmanTree(nodes);
		// 对应的赫夫曼编码(根据 赫夫曼树)
		Map<Byte,String> huffmanCodes = getCodes(huffmanTreeRoot);
		// 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
		return zip(bytes,huffmanCodes);
	}
	
	// 步骤五内容-----------------------------------------------------
	/**
	 * 将 原始数据(字符串)，通过赫夫曼编码表，压缩 成新的字节数组返回
	 * 
	 * eg：huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
	 * @param bytes			原始数据(字符串)对用的字节数组 
	 * @param huffmanCodes	原始数据生成的赫夫曼编码表
	 * @return				返回压缩处理后的字节数组
	 */
	private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes) {
		
		// 用于记录压缩后的新字节数据(既 通过huffmanCodes 将 bytes 转成字符串)
		StringBuilder stringBuilder = new StringBuilder();
		for(Byte b:bytes) {
			stringBuilder.append(huffmanCodes.get(b));
		}
		// 
		// System.out.println(stringBuilder.toString());
		
		// 计算 huffmanCodeBytes 的长度
		// 以下推导出的公式  int len = (stringBuilder.length() + 7)/8
		int len;
		if(stringBuilder.length()%8==0) {
			len = stringBuilder.length()/8;
		}else {
			len = stringBuilder.length()/8+1;
		}
		
		// 创建用于存储压缩后的 字节数组
		byte[] huffmanCodeBytes = new byte[len];
		int index = 0;// 记录是第几个 byte
		for (int i = 0; i < stringBuilder.length(); i+=8) {// 因为每位 8 位对应一个 byte，所有步长 为8
			String strByte;
			if(i+8>stringBuilder.length()) {// 不够8位( 若 i 是 1到7,说明它不够)
				strByte  = stringBuilder.substring(i);
			}else {
				strByte = stringBuilder.substring(i,i+8);
			}
			// 将 strByte 转成 一个byte，放入到huffmanCodeBytes 
			// 二进制的补码 ---》  反码  ---》 原码
			huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
			index++;
		}
		return huffmanCodeBytes;
	}
	
	
	// 步骤五内容-----------------------------------------------------

	
	
	// 步骤四内容-----------------------------------------------------
	// 步骤四：生成赫夫曼树对应的赫夫曼编码
	// 思路：1、将赫夫曼编码表存放到 Map<Byte,String>
	// eg：生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
	static Map<Byte,String> huffmanCodes = new HashMap<>();
	
	// 思路：2、在生成赫夫曼编码时，需要记录路径(拼接路径),定义StringBuilder,用于存储某叶子节点路径
	static StringBuilder huffmanRoute = new StringBuilder();
	
	/**
	 * 根据传入的 node 节点的所有叶子节点的赫夫曼编码得到，并存入 huffmanCodes 哈希表中
	 * @param node			获取编码表的节点		
	 * @param code			路径：规定 左子节点为 0，右子节点为 1
	 * @param huffmanRoute	用于拼接的路径
	 */
	private static void getCodes(Node node,String code,StringBuilder huffmanRoute) {
		// 辅助、递归的时候不会改变原始路径拼接
		StringBuilder stringBuilder = new StringBuilder(huffmanRoute);
		// 将 code 拼接到 stringBuilder
		stringBuilder.append(code);
		if(node!=null) {// 若为节点null，不处理
			// 判断当前节点，是叶子节点 还是非叶子节点
			if(node.data==null) {// 非叶子节点
				// 向左递归
				getCodes(node.left, "0", stringBuilder);
				// 向右递归
				getCodes(node.right, "1", stringBuilder);
			}
			else {// 说明是一个叶子节点
				// 说明已经找到某个叶子节点的最后
				huffmanCodes.put(node.data, stringBuilder.toString());
			}
		}
	}
	
	// 重载 getCodes ，方便调用
	public static Map<Byte, String> getCodes(Node root) {
		if(root==null) {
			return null;
		}
		// 处理 root 的左子树
		getCodes(root.left, "0", huffmanRoute);
		// 处理 root 的右子树
		getCodes(root.right, "1", huffmanRoute);
		
		return huffmanCodes;
	}

	// 步骤四内容-----------------------------------------------------
	
	
	// 步骤三：通过 节点集合，构建出赫夫曼树
	public static Node createHuffmanTree(List<Node> nodes) {
		// 循环四步骤，知道最终只有一个 root节点
		while (nodes.size() > 1) {
			// 从小到大排序
			Collections.sort(nodes);
			// 取出第一颗最小的二叉树（若是大到小，取第一颗最大）
			Node leftNode = nodes.get(0);
			// 取出第二颗最小的二叉树（若是大到小，取第二颗最大）
			Node rightNode = nodes.get(1);
			// 构建一颗新的二叉树，为以上两树的根节点(此树没有data,只有权值)
			Node parent = new Node(null, leftNode.weight + rightNode.weight);
			parent.left = leftNode;
			parent.right = rightNode;

			// 将处理完毕后的两颗二叉树，从 nodes 集合中删除
			// 并让 新构建出的二叉树，加入到 nodes 集合中，---循环中。。。
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}

		return nodes.get(0);
	}

	// 步骤二：将 字节数组 byte[] 转为 节点集合 List，用于后面构建赫夫曼树
	public static List<Node> getNodes(byte[] bytes) {

		// 创建一个要返回的节点集合
		List<Node> nodes = new ArrayList<Node>();

		// 遍历 bytes，统计每一个字节出现的次数,用 map<Byte,Integer>接收
		// key 为 Ascll 码值，value 为出现的次数
		Map<Byte, Integer> counts = new HashMap<>();
		for (byte b : bytes) {
			Integer count = counts.get(b);
			if (count == null) {
				// 当前是第一次进来，还没有这个数的次数（初始化）
				counts.put(b, 1);
			} else {
				counts.put(b, count + 1);
			}
		}

		// 将每个键值对，以 Node 节点对象的方式存储 到List集合中
		for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}

		// 返回
		return nodes;
	}

	// 调用节点自身的前序遍历
	public static void perOrder(Node root) {
		if (root == null) {
			System.out.println("抱歉，我TM无法遍历没有内容的根节点");
		} else {
			root.perOrder();
		}
	}

}

// 步骤一：创建Node节点(数据，权值，排序)
class Node implements Comparable<Node> {

	protected Byte data; // 存放数据(字符)本身，比如'a' => 97 ' ' => 32
	protected int weight; // 权值, 表示字符出现的次数
	protected Node left; // 左子树(默认null)
	protected Node right; // 右子树(默认null)

	@Override
	public int compareTo(Node o) {
		return this.weight - o.weight;
	}

	public Node(Byte data, int weight) {
		super();
		this.data = data;
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "Node [data=" + data + ", weight=" + weight + "]";
	}

	// 前序遍历
	public void perOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.perOrder();
		}
		if (this.right != null) {
			this.right.perOrder();
		}
	}
}